package com.leetcode.partition6;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/9/11 11:28
 */
public class LC600不含连续1的非负整数 {

    public static int findIntegers(int n) {
        return dynamicProgramming(n);
    }

    public static void main(String[] args) {
//        System.out.println(findIntegers(2));
//        System.out.println(findIntegers(3));
//        System.out.println(findIntegers(4));
        System.out.println(findIntegers(5));
    }

    /**
     * 转化为01字典树，例如6的二进制是110，且该树必定是小于等于n的完全二叉树
     *          110
     *        /     \
     *      0         1
     *     / \      /  \
     *    0   1    0    1
     *   /\  /\   /\    /
     *  0 1 0 1  0  1  0
     * 如果01字典树的一个结点的度为2，那么左子结点是根结点为0的满二叉树，右子结点是根结点为1的完全二叉树
     * 在高度为t，根结点为0的满二叉树中，其左子树是高度为t-1，根结点为0的满二叉树；其右子结点是高度为t-1，根结点为1的完全二叉树
     * 因为路径不能包含连续的1，所以右子结点只有其左子结点包含的从根结点到叶子结点的才符合条件，此时是高度为t-2，根结点为0的满二叉树
     * dp[i]：树高度为i-1，根结点为0的满二叉树中，不包含连续1的从根结点到叶子结点的数量
     * 状态转移方程式：dp[i] = dp[i - 1] + dp[i - 2]
     * 初始化：dp[1]=1，dp[0]=1
     *
     */
    private static int dynamicProgramming(int n) {
        int height = Integer.toBinaryString(n).length();
        int[] dp = new int[height + 2];
        dp[0] = dp[1] = 1;
        for (int i = 2; i < dp.length; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        System.out.println(Arrays.toString(dp));
        int prev = 0, answer = 0;
        //从n的最高位开始遍历（从二叉树的跟结点开始遍历），例如5=0101，则遍历0 1 0 1
        for (int i = height; i >= 0; i--) {
            int current = (n >> i) & 1;     //判断当前结点是0还是1
            if (current == 1) {             //如果当前结点是1，说明该层有左右子树，且左子树为满二叉树
                answer += dp[i + 1];        //加上左子树的结果
            }
            if (prev == 1 && current == 1) break;        //出现连续的1
            prev = current;
            //如果当前位是0，那么没有右子树，且左子树不一定是满二叉树，需要遍历下一层判断
            if (i == 0) answer++;
        }
        return answer;
    }
}
